/////////////// INTERPRETER

function RuntimeException(msg) {
  this.toString = function() {
    return msg;
  };
}

function NativeDefinitionBody(nativeFunction) {
  this.nativeFunction = nativeFunction;
}

function CustomDefinitionBody(phraseNode) {
  this.phraseNode = phraseNode;
}

function SymbolTable() {
  
  var natives = {};
  var customs = {};
  
  this.set = function(name, def) {
    if (def instanceof CustomDefinitionBody) {
      customs[name] = def;
    }
    else if (def instanceof NativeDefinitionBody) {
      natives[name] = def;
    }
    else {
      throw new RuntimeException("Symbol Table does not recognize definition type");
    }
    
  };
  
  this.get = function(name) {
    if(customs[name]) {
      return customs[name];
    }
    else {
      return natives[name];
    }
  };
  
  this.emptyCustomDefinitions = function() {
    customs = {};
  };
  
  this.toString = function() {
    
    var output = "";
    
    [natives,customs].forEach(function(table) {
      for (var name in table) {
        output += name + " = ";
      
        var definition = table[name];
      
        if (definition instanceof CustomDefinitionBody) {
          output += definition.phraseNode.toString();
        }
        else if (definition instanceof NativeDefinitionBody) {
          output += "<native definition>";
        }
        else {
          output += "<unknown>";
        }
      
        output += "\n";
      }
    });
    
    return output;
  };
  
}

function RuntimeStack() {

  var array = [];
  
  this.top = function() {
    if (array.length === 0) {
      throw new RuntimeException("Stack empty");
    }  
    return array[array.length - 1];
  };
  
  this.pop = function() {
    if (array.length === 0) {
      throw new RuntimeException("Stack empty");
    }  
    return array.pop();
  };
  
  this.push = function(value) {
    if (array.length > 1000) {
      throw new RuntimeException("Stack has reached limit of 1000 items; Operation terminated");
    }
    array.push(value);
  };
  
  this.drop = function(position) {
    if (!Extras.isBetween(0, position, array.length - 1)) {
      throw new RuntimeException("Attempted drop outside of stack bounds; stack size = " + array.length + "; position = " + position.toString());
    }
    if (!Extras.isInteger(position)) {
      throw new RuntimeException("Drop expects non-negative integer, got: " + position.toString());
    }
    array.splice(array.length - 1 - position, 1);
  };
  
  this.duplicate = function(position) {
    if (!Extras.isBetween(0, position, array.length - 1)) {
      throw new RuntimeException("Attempted duplication outside of stack bounds; stack size = " + array.length + "; position = " + position.toString());
    }
    if (!Extras.isInteger(position)) {
      throw new RuntimeException("Duplication expects non-negative integer, got: " + position.toString());
    }
    array.push(array[array.length - 1 - position]);
  };
  
  this.rotate = function (n) {
    if (n > array.length) {
      throw new RuntimeException("Attempted to rotate more items than on stack; stack size = " + array.length + "; number to rotate = " + n);
    }
    array.push(array.splice(array.length - n, 1)[0]);
  };
  
  this.empty = function () {
    array = [];
  };
  
  this.toString = function() {
    return array.mapMethod("toString").join(" ");
  };            

}

function Interpreter(stack, symbolTable, print) {

  createNativeDefinition("apply", runApply);
  createNativeDefinition("+", runBinaryMathOp("+", "+"));
  createNativeDefinition("-", runBinaryMathOp("-", "-"));
  createNativeDefinition("*", runBinaryMathOp("*", "*"));
  createNativeDefinition("/", runBinaryMathOp("/", "/"));
  createNativeDefinition("<", runBinaryCompOp("<", "<"));
  createNativeDefinition(">", runBinaryCompOp(">", ">"));
  createNativeDefinition("<=", runBinaryCompOp("<=", "<="));
  createNativeDefinition(">=", runBinaryCompOp(">=", ">="));
  createNativeDefinition(".", runOpPrint);
  createNativeDefinition("eq", runBinaryCompOp("===", "eq"));
  createNativeDefinition("dup", runDup);
  createNativeDefinition("dup#", runDupNumber);
  createNativeDefinition("ifte", runIfte);
  createNativeDefinition("swap", runSwap);
  createNativeDefinition("drop", runDrop);
  createNativeDefinition("drop#", runDropNumber);
  createNativeDefinition("cat", runConcatenateBlock);
  createNativeDefinition("block", runCreateBlock);
  createNativeDefinition("block#", runCreateBlockNumber);
  createNativeDefinition("rot", runRotateTopNElements(3));
  
  this.run = function(programNode) {
    programNode.statements.forEach(function(statement){
   
      if (statement instanceof DefinitionStatementNode) {
        runDefinition(statement);
      }
      else if (statement instanceof PhraseStatementNode) {
        runPhrase(statement, 0);
      }
      else {
        throw new RuntimeException("Unrecognized statement: <" + statement.toString() + ">");
      }

    });
  };
  
  function runPhrase(phraseNode, recursionCount) {
    if (recursionCount > 100) {
      throw new RuntimeException("Possible infinite recursion detected; Operation terminated");
    }
    runNestableNodes(phraseNode.nodes, recursionCount);
  }
  
  function runNestableNodes(nestableNodesArray, recursionCount) {
    nestableNodesArray.forEach(function(nestableNode) {
      if (nestableNode instanceof BlockNode) {
        runBlock(nestableNode);
      }
      else if (nestableNode instanceof NameNode) {
        runName(nestableNode.val, recursionCount);
      }
      else if (nestableNode instanceof NumberNode) {
        runNumber(nestableNode.val);
      }
      else {
        throw new RuntimeException("Unrecognized nested node: <" + nestableNode.toString() + ">");
      }
    });
  }  

  function runDefinition(definitionNode) {
    symbolTable.set(definitionNode.name, new CustomDefinitionBody(definitionNode.body));
  }

  function runBlock(blockNode) {
    stack.push(blockNode);
  }
  
  // Methods to execute atoms
  
  function runNumber(numberValue) {
    stack.push(new NumberNode(numberValue));
  }
    
  function runName(nameString, recursionCount) {
    var definition = symbolTable.get(nameString);
  
    if (definition instanceof CustomDefinitionBody) {
      runPhrase(definition.phraseNode, recursionCount + 1);
    }
    else if (definition instanceof NativeDefinitionBody) {
      definition.nativeFunction();
    }
    else {
      throw new RuntimeException("Undefined name: " + nameString);
    }
  }
  
  function runOpPrint() {
    var x = stack.pop();

    if (x instanceof NumberNode) {
      print(x.toString());
    }
    else if (x instanceof BlockNode) {
      print(x.toString());
    }
    else {
      throw new RuntimeException("'.' expects number or block, got: <" + x.toString() + ">");
    }
  }
  
  function runBinaryMathOp(opString, opRepresentation) {
    return function(){
      var y = stack.pop();
      var x = stack.pop();
  
      if (x.toNumberValue && y.toNumberValue) {
        // Spaces must be here or negative numbers can cause problem
        var result = eval(x.toNumberValue().toString() + " " + opString + " " + y.toNumberValue().toString());
        stack.push(new NumberNode(result));
      }
      else {
        throw new RuntimeException("'" + opRepresentation + "' expects two numbers, got: <" + x.toString() + "> and <" + y.toString() + ">");
      }
    };
  }

  function runBinaryCompOp(opString, opRepresentation) {
    return function(){
      var y = stack.pop();
      var x = stack.pop();
  
      if (x.toNumberValue && y.toNumberValue) {
        var result = eval(x.toNumberValue().toString() + opString + y.toNumberValue().toString());
        if (result === true) {
          stack.push(new NumberNode(1));
        }
        else {
          stack.push(new NumberNode(0));
        }
      }
      else {
        throw new RuntimeException("'" + opRepresentation + "' expects two numbers, got: <" + x.toString() + "> and <" + y.toString() + ">");
      }
    };
  }
  
  function runDup() {
    stack.duplicate(0);
  }
  
  function runDupNumber() {
    var x = stack.pop();
    
    if (x.toNumberValue) { // Can x be converted to a number value?
      var position = x.toNumberValue();
      stack.duplicate(position);
    }
    else {
      throw new RuntimeException("'dup#' expects number, got: <" + x.toString() + ">");
    }   
  }

  function runSwap() {
    var x = stack.pop();
    var y = stack.pop();
    stack.push(x);
    stack.push(y);
  }

  function runApply() {
    var x = stack.pop();
            
    if (x instanceof BlockNode) {
      runNestableNodes(x.nodes);
    }
    else {
      throw new RuntimeException("'apply' expects block, got: <" + x.toString() + ">");
    }
  }

  function runIfte() {
    var pelse = stack.pop();
    var pthen = stack.pop();
    var pif = stack.pop();

    if (BlockNode.hasInstances(pif,pthen,pelse)) {
      // eval if
      stack.push(pif);
      runApply();
      var predicateResult = stack.pop();
      
      if (predicateResult.toBooleanValue) { // Can predicateResult be converted to a boolean value?
        if (predicateResult.toBooleanValue()) {
          stack.push(pthen);
        }
        else {
          stack.push(pelse);
        }
        runApply();
      }
      else {
        throw new RuntimeException("'ifte' expected boolean, got: <" + predicateResult.toString() + ">");
      }
    }
    else {
      throw new RuntimeException("'ifte' expects three blocks, got: <" + pif.toString() + ">, <" + pthen.toString() + ">, and <" + pelse.toString() + ">");
    }
  }
  
  function runDropNumber() {
    var x = stack.pop();
  
    if (x.toNumberValue) { // Can x be converted to a number value?
      var position = x.toNumberValue();
      
      if (Extras.isInteger(position) && (position >= 0)) {
        stack.drop(position);
      }
      else {
        throw new RuntimeException("'drop#' expects non-negative integer, got: <" + x.toString() + ">");
      }      
    }
    else {
      throw new RuntimeException("'drop#' expects number, got: <" + x.toString() + ">");
    }    
  }
  
  function runDrop() {
    stack.pop();
  }
  
  function runConcatenateBlock() {
    var y = stack.pop();
    var x = stack.pop();
    
    if (x instanceof BlockNode && y instanceof BlockNode) {
      stack.push(x.concatenatedWith(y));
    }
    else {
      throw new RuntimeException("Concatenation expects two blocks, got: <" + x.toString() + "> and <" + y.toString() + ">");
    }
  }
  
  function runCreateBlock() {
    runCreateBlockOnStack(2);
  }
  
  function runCreateBlockNumber() {
    var x = stack.pop();
  
    if (x.toNumberValue) { // Can x be converted to a number value?
      var length = x.toNumberValue();
      
      if (Extras.isInteger(length) && (length >= 0)) {
        runCreateBlockOnStack(length);
      }
      else {
        throw new RuntimeException("'join#' expects non-negative integer, got: <" + x.toString() + ">");
      }
    }
    else {
      throw new RuntimeException("'join#' expects number, got: <" + x.toString() + ">");
    }
  }
  
  function runRotateTopNElements(n) {
    return function () {
      stack.rotate(n);
    };
  }
  
  function runCreateBlockOnStack(length) {
    var nodesArray = [];
    
    if (length > 0) {
      Extras.range(length - 1).forEach(function(){
        nodesArray.unshift(stack.pop());
      });
    }
    
    stack.push(new BlockNode(nodesArray));
  }
  
  // Helper functions
  
  function createNativeDefinition(nameString, nativeFunction) {
    symbolTable.set(nameString, new NativeDefinitionBody(nativeFunction));
  }
}